#include <iostream>
#include <vector>
using namespace std;

// 判断x是否质数，返回true表示x是质数，否则返回false
bool isPrime(int x) {
    if (x < 2) return false;
    for (int p = 2; p < x; p++) { 
        if (x % p == 0)
            return false; // 找到p为x的因子，x不是质数
    }
    return true; // 未找到因子，x为质数
}

// 方法1：求n以内的所有质数并输出
void listPrimes1(int n) {
    for (int x = 2; x <= n; x++) {
        if (isPrime(x)) // 判断是否质数的算法在isPrime方法中实现
            cout << " " << x;
    }
    cout << endl;
}

// 方法2：备忘录优化（埃拉托斯特尼筛法）
void listPrimes2(int n) {
    vector<bool> nums(n + 1, true);
    for (int x = 2; x <= n; x++) {
        if (nums[x]) { // x为质数
            cout << " " << x; // 输出质数
            for (int y = x + x; y <= n; y += x) {
                nums[y] = false; // x的倍数均为合数
            }
        }
    }
    cout << endl;
}

int main() {
    cout << "请输入n，让我计算n以内的所有质数：";
    int n;
    cin >> n;

    listPrimes2(n); // 使用备忘录优化的方法

    return 0;
}